package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 20:35 2020/8/10
 * @Description
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class InorderTraversal {

    /**
     * 左 中 右
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            ans.add(p.val);
            p = p.right;
        }
        return ans;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
